/**
 * Created with IntelliJ IDEA.
 * Description://移动零、左叶子节点之和、快乐数、盛最多水的容器
 * Date: 2024-02-15
 * Time:7:27
 */
public class Solution {
    public void moveZeroes(int[] nums) {
        int notZeroCount = 0;
        int fast = 0,slow = 0;
        for(;fast<nums.length;fast++) {
            if(nums[fast] != 0) {
                nums[slow++] = nums[fast];
                notZeroCount++;
            }
        }
        int zeroCount = nums.length - notZeroCount;
        while(zeroCount-- >0) {
            nums[slow++] = 0;
        }
    }
//////////////////////////////////////////////////////////
/*
    private void move(int pos,int[] arr) {
        for(int i = arr.length-2;i >= pos;i--) {
            arr[i+1] = arr[i];
        }
    }
*/
////////////////////////////////////////////////////////////
    //复写零
    public void duplicateZeros(int[] arr) {
        //通过快慢指针确定复写的位置
        int fast = 0,slow = 0;
        int len = arr.length;
        while(fast < len) {
            if(arr[fast] == 0)
                fast++;
            slow++;
            fast++;
        }
        //此时slow就是复写开始的位置
        int start = slow,end = len - 1;

        while(start >= 0) {

            if (arr[start] == 0) {
                arr[end--] = 0;
            }
            arr[end--] = arr[start--];
        }

    }
/////////////////////////////////////////////////////
    //路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null)
            return false;
        targetSum -= root.val;
        if(root.left == null && root.right == null) {
            if(targetSum == 0)
                return true;
            return false;
        }
        return hasPathSum(root.left,targetSum) || hasPathSum(root.right,targetSum);
    }



    /////////////////////////////////////////////////////
    //左叶子的和
    public int sumOfLeftLeaves(TreeNode root) {
        TreeNode parent = root;
        int ret = traversal(root,false);//一开始传false，因为只有一个节点时不算作左节点
        return ret;
    }

    private int traversal(TreeNode root,boolean isLeft) {  //isLeft筛选出左叶子节点
        //前序遍历
        if(root == null)
            return 0;
        if(isLeft && root.left == null && root.right == null) {
            return root.val;
        }

        int left = traversal(root.left,true);  //左子树中的左叶子
        int right = traversal(root.right,false);  //右子树中的左叶子
        return left + right;
    }
    ////////////////////////////////////////
    //快乐数
    public boolean isHappy(int n) {
        int slow = n;
        int fast = change(slow);
        while(fast != slow) {
            slow = change(slow);
            fast = change(slow);
        }
        if(fast == 1)
            return true;
        else
            return false;
    }

    private int change(int num) {
        int newNum = 0;
        while(num != 0) {
            int singleNum = num % 10;
            newNum += singleNum * singleNum;
            num /= 10;
        }
        return newNum;
    }
    ////////////////////////////////////////////////
    //盛最多水的容器
    public int maxArea(int[] height) {
        int left = 0,right = height.length-1;
        int area = 0;
        while(left != right) {
            int minHeight = Math.min(height[left], height[right]);
            int tmp = minHeight * (right - left);
            if(tmp > area)
                area = tmp;
            if(height[left] < height[right])
                left++;
            else
                right--;
        }
        return area;
    }
    /////////////////////////////////////


}
